/*
 * The RavenX Library
 * Copyright (c) 2008 by Solidus
 * 
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.It is provided "as is" without express 
 * or implied warranty.
 *
 */


#ifndef RX_AVL_TREE_H
#define RX_AVL_TREE_H

#include "rx_typedef.h"


RX_SPACE_BEG




typedef struct __rx_avltree_node_tag		rx_avltree_node_t;

typedef struct __rx_avltree_tag			rx_avltree_t;


RavenAPI rx_avltree_node_t* rx_avltree_previous(rx_avltree_node_t *node);
RavenAPI rx_avltree_node_t* rx_avltree_successor(rx_avltree_node_t *node);

RavenAPI void*			   rx_avltree_node_data(rx_avltree_node_t *node);

RavenAPI rx_avltree_node_t* rx_avltree_leftmost(rx_avltree_t *self);
RavenAPI rx_avltree_node_t* rx_avltree_rightmost(rx_avltree_t *self);



RavenAPI rx_avltree_t*	rx_avltree_create(const rx_info_t *info, const rx_alloc_t *palloc);
RavenAPI void			rx_avltree_destroy(rx_avltree_t *self);
RavenAPI size_t			rx_avltree_size(const rx_avltree_t *self);
RavenAPI rx_avltree_t*	rx_avltree_copy(const rx_avltree_t *self);

RavenAPI rx_avltree_node_t* rx_avltree_insert_unique(rx_avltree_t *self, const void *data);
RavenAPI rx_avltree_node_t* rx_avltree_insert_equal(rx_avltree_t *self, const void *data);

RavenAPI rx_avltree_node_t* rx_avltree_erase_node(rx_avltree_t *self, rx_avltree_node_t *node);
RavenAPI rx_avltree_node_t* rx_avltree_erase_range(rx_avltree_t *self, rx_avltree_node_t *first, rx_avltree_node_t *last);

RavenAPI size_t	rx_avltree_erase_key(rx_avltree_t *self, const void *key);

RavenAPI void	rx_avltree_clear(rx_avltree_t *self);

RavenAPI rx_avltree_node_t* rx_avltree_find(rx_avltree_t *self, const void *key);
RavenAPI rx_avltree_node_t* rx_avltree_lower_bound(rx_avltree_t *self, const void *key);
RavenAPI rx_avltree_node_t* rx_avltree_upper_bound(rx_avltree_t *self, const void *key);

RavenAPI size_t	 rx_avltree_node_count(const rx_avltree_t *self, const void *key);

/*oper_f(data), left_most -> right_most*/
RavenAPI void rx_avltree_map(rx_avltree_t *self, void (*oper_f)(void *data));






#if defined(RX_DEBUG)


RavenAPI void rx_avltree_print(const rx_avltree_t *self, rx_print_func_t print_f, rx_trace_func_t trace_f);

RavenAPI rx_bool rx_avltree_verify(const rx_avltree_t *self);

#else

#define rx_avltree_print RX_NOOP


#define rx_avltree_verify RX_NOOP



#endif














RX_SPACE_END


#endif


